A set of m vectors {v₁,v₂, ...,v_m} in R^d (the set of d-tuples of real numbers) is said to be linearly independent if the only reals λ₁,λ₂,...,λ_m that satisfy λ₁ v₁ + λ₂ v₂ + ... + λ_m v_m = 0 are λ₁ = λ₂ = ... = λ_m = 0. For example, in R² the set of vectors {(1 0), (0 1)} is linearly independent. However, {(1 0), (0 1), (1 1)} is not since 1 ∙ (1 0) + 1 ∙ (0 1) + (-1) ∙ (1 1) = (0 0).

In this task, you are given n vectors in R^d, and every vector has some weight. Your job is to find a linearly independent set of vectors with maximal sum of weights.

The first line contains two integers d and n. The next n lines contain d+1 integers each, separated with one empty space between any two integers. The first d numbers in the line i+1 are coordinates of the i^th vector, and the last number is its weight.

The output should consist a single integer: the sum of weights of vectors in your set.

• 1 ≤ d ≤ 200
• 1 ≤ n ≤ 500
• The coordinates of the vectors are integers in the range [-10³,10³].
• The weights of the vectors are integers in the range [-10⁶,10⁶].